/*
 * Infix to postfix
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct stack{
    char block[100];
    int p;
};

void push(struct stack * stk, char item){
    stk->block[(stk->p)++] = item;
}

char pop(struct stack * stk){
    return stk->block[--(stk->p)];
}

char top(struct stack * stk){
    return stk->block[(stk->p-1)];
}

int is_empty(struct stack * stk){
    return (stk->p == 0);
}

void init(struct stack * stk){
    stk->p = 0;
}

struct node{
    char name;
    struct node * lchild;
    struct node * rchild;
};

int is_op(char chr){
    return  chr == '+' ||
            chr == '-' ||
            chr == '*' ||
            chr == '/' ||
            chr == '(' ||
            chr == ')'
            ;
}

int priority[128] = {
    ['+'] = 1,
    ['-'] = 1,
    ['*'] = 2,
    ['/'] = 2,
};

/*
 * for example "a+b*c+(d*e+f)*g"
 */
char * infix_to_postfix(char * expr){
    struct stack stk;
    int i;
    int len = strlen(expr);
    char * result = (char *) malloc(sizeof(char)*(len+1));
    int cur_p = 0;
    init(&stk);
    for(i=0; i<len; i++){
        if (!is_op(expr[i])){
            result[cur_p++] = expr[i];
        }else{
            if(expr[i] == '('){
                push(&stk, expr[i]);
            } else if (expr[i] == ')'){
                while(top(&stk) != '(') {
                    result[cur_p++] = pop(&stk);
                }
                pop(&stk);
            } else {
                while(!is_empty(&stk) && top(&stk) != '(' && \
                        priority[top(&stk)] >= priority[expr[i]]){
                        result[cur_p++] = pop(&stk);
                    }
                push(&stk, expr[i]);
            }
        }
    }
    while(!is_empty(&stk) ){
        result[cur_p++] = pop(&stk);
    }
    result[cur_p++] = '\0';
    return result;
}

int main() {
    char str[] = "a+b*c+(d*e+f)*g";
    char * result = infix_to_postfix(str);
    printf("%s\n",result);
    return 0;
}
